package nc;

import org.junit.Test;

public class Vivo {
    public int solution1 (int n) {
        int cur = 0;
        int add = 1;
        int cnt = 0;
        while (cur + add <= n) {
            cur += add;
            cnt += add * add;
            add++;
        }
        cnt += add * (n - cur);
        return cnt;
    }

    @Test
    public void test() {
        System.out.println(solution(4));
    }

    public int solution (int n) {
        int d = 1;
        int res = 0;
        while (n > 9) {
            boolean flag = true;
            for (int i = 9; i >= 2; i--) {
                if (n % i == 0) {
                    flag = false;
                    n /= i;
                    res += (i * d);
                    d *= 10;
                    break;
                }
            }
            if (flag) {
                return -1;
            }
        }
        res += n * d;
        return res;
    }

    @Test
    public void test1() {
        System.out.println(solution(100));
    }


    private static int[] ans = new int[10];
    private int[][] directs = new int[][]{
        {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}, //八方邻点
        {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-2, 1}, {-1, 2}, {-1, -2}, {-2, -1} //日字方向
    };
    public int solution(int m, int n) {
        int res = 0;
        for (int i = m; i <= n; i++) {
            res += count(i);
        }
        return res;
    }

    private int count(int n) {
        if (ans[n] > 0) {
            return ans[n];
        }
        for (int i = 1; i <= 3; i++) {
            for (int j = 1; j <= 3; j++) {
                dfs(1, i, j, new boolean[4][4]);
            }
        }
        return ans[n];
    }
    
    //idx:当前遍历到的深度
    //对于每个idx都将idx位置的ans[idx]++,意味着，一轮计算出所有的count 
    private void dfs(int idx, int i, int j,boolean[][] flag) {
        if (idx == 9) {
            ans[idx]++;
            return;
        }
        ans[idx]++;
        flag[i][j] = true;
        for (int k = 0; k < 16; k++) {
            int m = i + directs[k][0], n = j + directs[k][1];
            if (inArea(m, n)) {
                if (!flag[m][n]) {
                    dfs(idx + 1, m, n, flag);
                } else if (k < 8) {
                    //若是相邻的点，可以越过这个已经走过的点，再按同样的方向往前多走一步
                    m += directs[k][0];
                    n += directs[k][1];
                    if (inArea(m, n) && !flag[m][n]) {
                        dfs(idx + 1, m, n, flag);
                    }
                }
            }
        }
        flag[i][j] = false;
        return ;
    }

    private boolean inArea(int i, int j) {
        if (i < 1 || i > 3 || j < 1 || j > 3) {
            return false;
        }
        return true;
    }

    @Test
    public void test3() {
        // System.out.println(solution(3, 3));
        for (int i = 1; i <=9 ; i++) {
            System.out.println(count(i));
        }
    }
}